\chapter{Implémentation et expérimentation} % Main chapter title

\label{Chapter6} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 6. \emph{Implementation et expérimentation}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

Dans ce chapitre, nous abordons notre implémentation des algorithmes pour les consistances fortes. Plus particulièrement, ce sont les algorithmes : RPWC-1, rPIC-1, Max-RPWC-1, Max-RPWC-3. En suite, nous montrons le résultat expérimental et l'analyse de ce résultat est également donnée.
%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------
\section{Implémentation}

Comme nous avons présenté les algorithmes dans le chapitre \ref{Chapter4}, les contraintes nécessaires sont sollicitées pendant la propagation et dans la fonction  $Revise(x_j, c_i, DFC)$, les contraintes $c_m$ intersectées avec $c_i$ sont également sollicitées. Compte tenu de l'architecture d'AbsCon, nous faisons deux classes principales pour la propagation : 

\begin{itemize}
\item DFC : Elle permet d'appeler la propagation et de trouver les intersections entre les contraintes.
\item ConstraintHardExtensionDFC (DFC : RPWC1, rPIC1,\dots) : Cette classe représente les contraintes de CSP. A chaque fois, quand la contrainte est sollicitée. La méthode \textit{runPropagator(Variable)} de cette classe est appelée. Cette méthode joue le rôle de la $fonction Revise(x_j, c_i,DFC)$. 
\end{itemize}

%------------------------------------------------
Ci-dessous l'idée de la méthode \textit{runPropagator(Variable)}. Quand la contrainte $c_i$ est sollicitée, la fonction \textit{$c_i$.runPropagator(Variable)} est appelée. Elle révise la consistance (RPWC, rPIC, \dots) pour chacune de ses variables. La fonction \textit{Revise($x_j, c_i,DFC$)} est intégrée dans cette méthode.\\

\begin{lstlisting}[caption=function runPropagator(Variable)]
function $c_i$.runPropagator(Variable)
   for each variable $x_j \in c_i$ 
      Revise($x_j, c_i,DFC$)
   // update domain of all variable in $c_i$, return false if a domain of variable is empty   
   return updateDomain()
\end{lstlisting}

Dans ce travail, nous avons implémenté les algorithmes : RPWC-1, rPIC-1, Max-RPWC-1, Max-RPWC-3. L'algorithme Max-RPWC-2 n'a pas été implémentée car sa complexité d'espace est grande. Pour vérifier la correction de notre implémentation, nous avons testé le résultat avec les algorithmes ayant été implémenté dans AbsCon comme \textit{GAC} (l'algorithme STR2) et l'algorithme pour \textit{PWC+GAC}.
%----------------------------------------------------------------------------------------
%	SECTION 2
%----------------------------------------------------------------------------------------
\section{Expérimentation}
L'expérimentation est lancé avec le solveur AbsCon sur un PC de 4GB RAM, Core i5-2520M, Ubuntu. Les problèmes utilisés sont \textit{renault, random-fcd} dans \cite{problem}. Ce sont des problèmes utilisés pour la compétition de solveur de CSP \cite{problem2}. Le nombre de variables intersectées dans les contraintes de ces problèmes est varié entre 2 et 10. Nous comparons les algorithmes : RPWC, rPIC, MaxRPWC1, MaxRPWC3, GAC(algorithme STR2) et PWC+GAC(intégré dans AbsCon). Les critères à considérer sont CPU time(s), et node(n). Pour la recherche, l'heuristique \textit{dom/ddeg} pour choisir la variable, et la lexicographique pour choisir la valeur de cette variable. L'heuristique \textit{dom/ddeg} est choisie car le résultat est plus facile à comparer la puissance d'élagage des algorithmes.

La table ~\ref{table:modifiedRenault} montre le résultat sur les instances du problème \textit{modified renault}. Dans chaque carré, le temps d'exécution (s) et le nombre de node (n) sont montré. L'arité de chaque contrainte varie entre 2-10. Quand on considère le nombre de nœuds découverts (n), l’algorithme GAC doit passer le maximum de noeud, ensuite, ce sont les algorithmes RPWC1, rPIC1, Max-RPWC1, Max-RPWC3. L'algorithme PWC+GAC passe le minimum nombre de noeud par rapport aux autres algorithmes. Ce résultat correspond bien à la théorique parce que la puissance d'élagage de chaque consistance permet de réduire le nombre de noeuds passés. La puissance de PWC est la plus forte, l'algorithme pour cette consistance passe le moins nombre de noeuds. Dans les instances \textit{renault-3} et \textit{renault-5}, cette puissance est clairement montrée. Au niveau du temps d'exécution, les algorithmes RPWC1, rPIC1, Max-RPWC1, Max-RPWC3 sont moins compétitifs. Le temps d'exécution de ces algorithmes sont souvent plus lent par rapport à GAC (STR2) sauf les instances \textit{renault-3, renault-5}. Cela peut être expliquée par la complexité des algorithmes. A chaque noeud, le temps pour exécuter ces algorithmes est plus long que celui de l'algorithme GAC (STR2). Entre deux algorithmes : Max-RPWC1 et Max-RPWC3, l'algorithme Max-RPWC3 est souvent plus rapide que Max-RPWC1.


\begin{table}[h]
\centering
    \scalebox{0.95}{
    \begin{tabular}{ | l | p{0.3cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} |}
    \hline
    Problème  & & GAC (STR2)       & RPWC1 		& rPIC1 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    renault-0 & t n & \textbf{0.72}, 166  & 4.336, 114 	& 21.60, \textbf{111} & 51.17, \textbf{111} & 65.25, \textbf{111} & 3.29, \textbf{111}\\ \hline
    renault-1 & t n & 2.91, 53775  & 285.73, 43244& 118.00, 818 & 32.44, \newline\textbf{0} & 20.66, \newline\textbf{0} & \textbf{1.72,\newline 0}\\ \hline
    renault-2 & t n & \textbf{0.77}, \textbf{111} & 1.65, \textbf{111} & 31.17, \textbf{111} & 37.07, \textbf{111} & 47.49, \textbf{111} & 2.03, \textbf{111} \\ \hline
    renault-3 & t n & 1390.86, 20994648 & 17872.2, 16992656 & $>$36000, - & 30.00, \newline\textbf{0} & 45.80, \newline\textbf{0} & \textbf{1.52, \newline0}\\ \hline
    renault-4 & t n & \textbf{0.67}, 114 & 1.64, \textbf{112} & 22.93, \textbf{112} & 34.55, \textbf{112} & 30.60, \textbf{112} & 2.17, \textbf{112}\\ \hline
    renault-5 & t n & 213.82, 3231085 & 409.95, 44491& 647.82, 12825 &  102.09, 241 & 98.84, 241 & \textbf{1.57, \newline 0}\\ \hline
    renault-6 & t n & \textbf{4.64}, 115411 & 289.72, 59526 & 985.77, 59507 & 522.77, \textbf{52831} & 569.82, \textbf{52831} & 6.45, \textbf{52831}\\ \hline
    renault-7 & t n &  \textbf{0.70}, 134 & 3.50, 120& 28.33, 113&  42.17, 113 & 43.26, 113 & 2.06, \textbf{112}\\ \hline
    renault-8 & t n & 5.67, 180955 & 608.05, 111363 & 1745.68, 86045 & 456.98, 12336 & 257.66, 12336 & \textbf{2.24, \newline0}\\ \hline
    renault-9 & t n & \textbf{0.68}, 254 & 2.70, 148& 30.75, 113 &  59.53, 113 & 32.84, 113& 1.86, \textbf{111}\\ \hline
    \end{tabular}
    }
    \caption{Résultat expérimental sur les instances du problème \textit{modified renault}}
    \label{table:modifiedRenault}
\end{table}

Nous avons expérimenté ensuite sur les instances du problème \textit{random-fcd}. Ces instances sont générées par le modèle RB \cite{xu2005simple}. Les instances difficiles sont choisies pour expérimenter. La table ~\ref{table:random-fcd} montre le résultat. Dans cette expérimentation, le temps d'exécution pour chaque algorithme est limité à 2000 secondes, si un algorithme dépasse ce temps, il est arrêté. Au niveau d'élagage, le nombre de noeud montre que PWC+GAC est le plus fort, puis MaxRPWC, rPIC, RPWC et GAC est le plus faible. Même avec la puissance d'élagage plus fort que celle de GAC, la complexité de temps des algorithmes RPWC, rPIC, Max-RPWC1, Max-RPWC3 sont encore assez grande. C'est pour cette raison, ces algorithmes ne peuvent pas résoudre tous les instances. Dans ce résultat, l'algorithme Max-RPWC3 est toujours plus rapide que  Max-RPWC1. L'algorithme PWC+GAC est compétitif avec GAC(STR2), pour quelques instances, il est plus rapide que GAC (STR2).

\begin{table}[h]
\begin{center}
\scalebox{0.95}{
    \begin{tabular}{ | p{3cm} | p{0.3cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} | p{1.4cm} |}
    \hline
    Problème  & & GAC (STR2)  	& RPWC1 		& rPIC1 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    rand-3-20-20-60-632-fcd-12 & t n & \textbf{182.90}, 442618  & - \newline - & - \newline - &- \newline - &- \newline - & 235.41, \textbf{141422}\\ \hline
    rand-3-20-20-60-632-fcd-13 & t n & 89.34, 291047  & 1627.96, 184029 & - \newline - & - \newline -  & - \newline - & \textbf{74.86, 111347}\\ \hline
    rand-3-20-20-60-632-fcd-22 & t n & 176.08, 357888  & 1538.05, 205691 	& - \newline - & - \newline -  & - \newline - & \textbf{166.37, 121615}\\ \hline
    rand-3-20-20-60-632-fcd-25 & t n & 65.04, 162524  & 680.60, 84636 	& - \newline - & 1911.18, 57987 & 1132.22, 57987 & \textbf{62.12, 57883}\\ \hline
    rand-3-20-20-60-632-fcd-26 & t n & 94.68, 314612  & 616.62, 104954 	& - \newline - & 1046.79, 28009 & 780.93, 28009 & \textbf{24.30, 20203}\\ \hline
    rand-3-20-20-60-632-fcd-27 & t n & 169.17, 447726  & 1835.56, 251913 	& - \newline - & - \newline - & - \newline - & \textbf{147.66, 111419}\\ \hline
    rand-3-20-20-60-632-fcd-2 & t n & \textbf{30.49}, 69199  & 225.20, 36131 & 1111.33, 30128 & 1026.40, 22830 & 627.17, 22830 & 35.57, \textbf{18248}\\ \hline
    rand-3-20-20-60-632-fcd-31 & t n & 88.56, 253745  & 559.61, 111407 & - \newline - & - \newline - & 1412.27, 80772 & \textbf{72.83, 77716}\\ \hline
    rand-3-20-20-60-632-fcd-32 & t n & \textbf{91.07}, 233802  & 1296.33, 155292 & - \newline -  & - \newline - & - \newline - & 100.09, \textbf{84892}\\ \hline
    rand-3-20-20-60-632-fcd-33 & t n & 239.85, 724656  & - \newline - & - \newline - & - \newline -  & - \newline -  & \textbf{195.73, 206415}\\ \hline
    rand-3-20-20-60-632-fcd-34 & t n & 68.79, 206031  &  840.33, 122238	& - \newline - & - \newline - & - \newline - & \textbf{62.45, 57367}\\ \hline
    rand-3-20-20-60-632-fcd-35 & t n & 9.21, 23546  & 84.60, 12079	& 457.52, 10542 & 384.65, 6914 & 231.16, 6914 & \textbf{6.76, 5165}\\ \hline
    rand-3-20-20-60-632-fcd-39 & t n & 48.75, 146557  & 808.11, 76763 	& - \newline - & 1515.00, 27827 & 1325.11, 27827 & \textbf{39.09, 27524}\\ \hline
    rand-3-20-20-60-632-fcd-3 & t n & \textbf{57.39}, 157061  & 725.5, 90875	& - \newline - & - \newline - & 1169.79, 63970 & 69.71, \textbf{58492} \\ \hline
    rand-3-20-20-60-632-fcd-40 & t n & 105.05, 252077  & 1119.37, 124814 	& - \newline - & - \newline - & - \newline - & \textbf{89.41, 65002}\\ \hline
    rand-3-20-20-60-632-fcd-50 & t n & 373.71, 1263148  & - \newline - & - \newline - & - \newline - & - \newline - & \textbf{198.65, 192628}\\ \hline
    \end{tabular}
}
\end{center}
\caption{Résultat expérimental sur les instances du problème \textit{random-fcd}}
\label{table:random-fcd}
\end{table}

Nous avons montré le résultat expérimental, entre les algorithmes étudiés dans ce travail, Max-RPWC3 est prometteur pour la pratique. Il est souvent plus rapide que Max-RPWC1 et rPIC1. Pour quelques instances, Max-RPWC3 est plus rapide que GAC (STR2). L'algorithme PWC+GAC (qui est déjà implémenté dans AbsCon) est compétitif par rapport aux autres algorithmes. Il est le plus rapide dans plusieurs instances et sa puissance d'élagage est plus forte que les autres dans ce travail.


%\begin{table}[h]
%\begin{center}
%\scalebox{0.95}{
%    \begin{tabular}{ | p{2cm} | p{0.3cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} |}
%    \hline
%    Problème  & & GAC (STR2)  	& RPWC1 		& rPIC1 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
%    dubois-100 & t n & -, -  & -, - & -, - & -, - & -, - & -, -\\ \hline
%    dubois-20 & t n & 23.07, 25690106  & 19.30, 2621434& 12.28, 2621434 & 12.13, 2621434 & 12.15, 2621434 & 15.56, 19398612\\ \hline
%    dubois-21 & t n & 68.69, 53477370  & 36.34, 5242874& 24.56, 5242874 & 29.22, 5242874 & 24.72, 5242874 & 37.26, 40370130\\ \hline
%    dubois-22 & t n & 112.93, 111149050  & 66.81, 10485754 & 51.58, 10485754 & 56.56, 10485754 & 55.54, 10485754 & 77.28, 83886032\\ \hline
%    dubois-23 & t n & 223.71, 230686714  & 149.52, 20971514 & 124.77, 20971514 & 101.01, 20971514 & 156.90, 20971514 & 177.85, 174063566\\ \hline
%    dubois-24 & t n & 494.19, 478150650  & 330.38, 41943034 & 221.39, 41943034 & 203.98, 41943034 & 276.17, 41943034 & 356.77, 360710092\\ \hline
%    dubois-25 & t n & 1099.33, 989855738  & 626.14, 83886074& 542.38, 83886074 & 410.77, 83886074 & 529.80, 83886074 & 710.21, 746586058\\ \hline
%    dubois-26 & t n & -, -  & 1511.64, 167772154 & 1197.05, 167772154 & 862.41, 167772154 & 1086.80, 167772154 & 1585.99, 1543503816\\ \hline
%    dubois-27 & t n & -, -  & -, -	& -, - & 1786.85, 335544314 & -, - & -, -\\ \hline
%    dubois-28 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
%    dubois-29 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
%    dubois-30 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
%    dubois-50 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
%    \end{tabular}
%}
%\end{center}
%\caption{Résultat expérimental sur les instances du problème \textit{dubois}}
%\label{table:dubois}
%\end{table}








